/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/valid-parentheses
   @Language: C++
   @Datetime: 16-02-09 05:24
   */

class Solution {
public:
	/**
	 * @param s A string
	 * @return whether the string is a valid parentheses
	 */
	bool isValidParentheses(string& s) {
		// Write your code here
		stack<char> strs;
		for(int i=0; i<s.length(); ++i){
			if (s[i]=='(' || s[i]=='[' || s[i]=='{')
				strs.push(s[i]);
			else if(strs.size()){
				if ((s[i]==')' && strs.top()=='(')
						|| (s[i]==']' && strs.top()=='[')
						|| (s[i]=='}' && strs.top()=='{'))
					strs.pop();
				else return false;
			}
			else return false;
		}
		return !strs.size();
	}
};
